#include "QuadTree.h"

QuadTree::QuadTree()
{
	root = NULL;
}
QuadTree::QuadTree(int pos_x, int pos_y, int size, int level)
{
	this->max_level = level;
	root = new QNode(pos_x, pos_y, size, 0, 0);
}

QuadTree::~QuadTree()
{
	if (root != NULL)
	{
		delete root;
	}
}

void QuadTree::clip(RECT camara_rect, QNode *p_qnode, list<Object*>* p_obj_list)
{
	bool is_clip = false;

	if (!(camara_rect.left + camara_rect.right < p_qnode->getX1() || camara_rect.left > p_qnode->getX2() || camara_rect.top + camara_rect.bottom < p_qnode->getY1() || camara_rect.top > p_qnode->getY2()))
	{
		is_clip = true;
	}
	else
	{
		is_clip = false;
	}

	if (is_clip == true)
	{
		//lay danh sach doi tuong cua qnode
		Object *obj;

		list<Object*>::const_iterator it;
		for (it = p_qnode->obj_list.begin(); it != p_qnode->obj_list.end(); it++)
		{
			obj = *it;

			if (obj->getObjState() != 0) //trang thai REMOVE
			{


				//////////////////////////////////////////////////////////////////////////
				//kiem tra xem obj da co trong p_obj_list hay chua?
				//neu co thi k them vao
				bool is_drawed = false;
				Object *obj_drawed;

				list<Object*>* obj_drawed_list = p_obj_list;
				list<Object*>::iterator i_obj_drawed = obj_drawed_list->begin();
				while (i_obj_drawed != obj_drawed_list->end() && is_drawed == false)
				{
					obj_drawed = *i_obj_drawed;
					if (obj->getIDObj() == obj_drawed->getIDObj())
					{
						is_drawed = true;

					}
					++i_obj_drawed;
				}
				//////////////////////////////////////////////////////////////////////////
				if (is_drawed == false)
				{
					//kiem tra obj nam khong qua xa camera: khac phuc tinh trang bi giat
					if (obj->getPosX() > camara_rect.left - 30 && obj->getPosX() < camara_rect.left + 800 + 30)
					{
						p_obj_list->push_back(obj);
					}

					//p_obj_list->push_back(obj); //hoi bi giat
				}
				//p_obj_list->push_back(obj);
			}
		}

		//list<Object*> const obj_list = p_qnode->getObjList();	//khai bao const trong truong hop bi loi iterator
		//list<Object*>::const_iterator it = obj_list.begin();
		//while (it != obj_list.end())
		//{
		//	obj = *it;
		//	//////////////////////////////////////////////////////////////////////////
		//	//kiem tra xem obj da co trong p_obj_list hay chua?
		//	//neu co thi k them vao
		//	bool is_drawed = false;
		//	Object *obj_drawed;

		//	list<Object*>* obj_drawed_list = p_obj_list;
		//	list<Object*>::iterator i_obj_drawed = obj_drawed_list->begin();
		//	while (i_obj_drawed != obj_drawed_list->end() && is_drawed == false)
		//	{
		//		obj_drawed = *i_obj_drawed;
		//		if (obj->getIDObj() == obj_drawed->getIDObj())
		//		{
		//			is_drawed = true;
		//			
		//		}
		//		++i_obj_drawed;
		//	}
		//	//////////////////////////////////////////////////////////////////////////
		//	if (is_drawed == false)
		//	{
		//		p_obj_list->push_back(obj);
		//	}
		//	
		//	++it;
		//}
	}
}

void QuadTree::getObjFromCamara(RECT camara_rect, list<Object*>* p_obj_list)
{
	getObjFromCamara(this->root, camara_rect, p_obj_list);

}

void QuadTree::getObjFromCamara(QNode *p_qnode, RECT camara_rect, list<Object*>* p_obj_list)
{

	if (p_qnode->getLeftTop() == NULL || 
		p_qnode->getRightTop() == NULL || 
		p_qnode->getLeftBottom() == NULL ||
		p_qnode->getRightBottom() == NULL)
	{
		//node con
		clip(camara_rect, p_qnode, p_obj_list);		 
	}
	else
	{
		getObjFromCamara(p_qnode->getLeftTop(), camara_rect, p_obj_list);
		getObjFromCamara(p_qnode->getRightTop(), camara_rect, p_obj_list);
		getObjFromCamara(p_qnode->getLeftBottom(), camara_rect, p_obj_list);
		getObjFromCamara(p_qnode->getRightBottom(), camara_rect, p_obj_list);
	}



}

void QuadTree::getObjList(list<Object*>* p_obj_list)
{
	getObjList(this->root, p_obj_list);
}

void QuadTree::getObjList(QNode *p_qnode, list<Object*>* p_obj_list)
{
	if (p_qnode->getLeftTop() == NULL || 
		p_qnode->getRightTop() == NULL || 
		p_qnode->getLeftBottom() == NULL ||
		p_qnode->getRightBottom() == NULL)
	{
		//node con
		//clip(camara_rect, p_qnode, p_obj_list);
		list<Object*> temp_list;
		temp_list = p_qnode->getObjList();
		Object *obj;
		list<Object*>::const_iterator iList;// = p_qnode->getObjList().begin();
		for (iList = temp_list.begin(); iList != temp_list.end(); iList++)
		{
			obj = *iList;
			p_obj_list->push_back(obj);
			//iList = temp_list.erase(iList);
		}
		/*while (iList != p_qnode->getObjList().end())
		{
		obj = *iList;
		p_obj_list->push_back(obj);
		iList++;
		}*/

		//return ;
	}
	else
	{
		getObjList(p_qnode->getLeftTop(), p_obj_list);
		getObjList(p_qnode->getRightTop(), p_obj_list);
		getObjList(p_qnode->getLeftBottom(), p_obj_list);
		getObjList(p_qnode->getRightBottom(), p_obj_list);
	}
}


// Background Game

void QuadTree::addAllTiles(char* matrix_file)
{
	string data;
	ifstream fileStream(matrix_file);
	if (fileStream.is_open())
	{
		while (!fileStream.eof())
		{
			data += fileStream.get();
		}
	}
	vector<string> dataSplit = Utility::split(data, '\n');
	string row_header = dataSplit[0];
	vector<string> element_row = Utility::split(row_header, ' ');

	int width, height;
	width = atoi(element_row[0].c_str());		//lay so cot thong tin obj
	height = atoi(element_row[1].c_str());		//so luong obj

	int index = 0;
	TilesObject* p_tiles = NULL;
	for (int i = 1; i <= height; i++)
	{
		string temp = dataSplit[i];
		vector<string> temp_vector = Utility::split(temp, ' ');

		for (int j = 0; j < width; j++)
		{
			index++;
			//id_type
			/*int tiles_id = atoi(temp_vector[j].c_str());
			int pos_x = j * 32;
			int pos_y = i * 32;*/
			p_tiles = new TilesObject(index, atoi(temp_vector[j].c_str()), j*32, i*32, 32);
						
			root->addTilesBg(p_tiles);
			/*delete p_tiles;
			p_tiles = NULL;*/
		}		
	}
}

void QuadTree::divide()
{
	build(root);
}

void QuadTree::build(QNode *p_qnode)
{
	if (p_qnode->getSize() <= 512)//256
	{
		return;
	}

	int size = p_qnode->getSize() / 2;

	QNode * leftTop = new QNode(p_qnode->getX1(), p_qnode->getY1(), size, p_qnode->getLevel() + 1, p_qnode->getIDNode() * 10 + 1);
	QNode * rightTop = new QNode(p_qnode->getX1() + size, p_qnode->getY1(), size, p_qnode->getLevel() + 1, p_qnode->getIDNode() * 10 + 2);
	QNode * leftBottom = new QNode(p_qnode->getX1(), p_qnode->getY1() + size, size, p_qnode->getLevel() + 1, p_qnode->getIDNode() * 10 + 3);
	QNode * rightBottom = new QNode(p_qnode->getX1() + size, p_qnode->getY1() + size, size, p_qnode->getLevel() + 1, p_qnode->getIDNode() * 10 + 4);

	p_qnode->setLeftTop(leftTop);
	p_qnode->setRightTop(rightTop);
	p_qnode->setLeftBottom(leftBottom);
	p_qnode->setRightBottom(rightBottom);

	TilesObject *tiles_temp;
	list<TilesObject*>::iterator i; 
	for (i = p_qnode->tilesBg_list.begin(); i != p_qnode->tilesBg_list.end(); i++)
	{
		tiles_temp = *i;
		clipToNode(tiles_temp, p_qnode->getLeftTop());
		clipToNode(tiles_temp, p_qnode->getRightTop());
		clipToNode(tiles_temp, p_qnode->getLeftBottom());
		clipToNode(tiles_temp, p_qnode->getRightBottom());
	}
	p_qnode->getTilesBgList().clear();

	//build cac node con
	build(p_qnode->getLeftTop());
	build(p_qnode->getRightTop());
	build(p_qnode->getLeftBottom());
	build(p_qnode->getRightBottom());
}

void QuadTree::clipToNode(TilesObject *p_tiles, QNode *p_qnode)
{
	bool is_clip = false;

	if (!(p_tiles->pos_x2 < p_qnode->getX1() ||
		p_tiles->pos_x > p_qnode->getX2() ||
		p_tiles->pos_y2 < p_qnode->getY1() ||
		p_tiles->pos_y > p_qnode->getY2()))
	{
		is_clip = true;
	}
	else
	{
		is_clip = false;
	}
	if (is_clip == true)
	{
		p_qnode->addTilesBg(p_tiles);
	}
}




void QuadTree::clipTiles(RECT camara_rect, QNode *p_qnode, list<TilesObject*>* p_tiles_list)
{
	bool is_clip = false;

	if (!(camara_rect.left + camara_rect.right < p_qnode->getX1() || camara_rect.left > p_qnode->getX2() || camara_rect.top + camara_rect.bottom < p_qnode->getY1() || camara_rect.top > p_qnode->getY2()))
	{
		is_clip = true;
	}
	else
	{
		is_clip = false;
	}

	if (is_clip == true)
	{
		//lay danh sach doi tuong cua qnode
		TilesObject *tiles;

		list<TilesObject*>::const_iterator it;
		for (it = p_qnode->tilesBg_list.begin(); it != p_qnode->tilesBg_list.end(); it++)
		{
			tiles = *it;

			//////////////////////////////////////////////////////////////////////////
			//kiem tra xem obj da co trong p_obj_list hay chua?
			//neu co thi k them vao
			//bool is_drawed = false;
			//TilesObject* tiles_drawed;

			//list<TilesObject*>* tiles_drawed_list = p_tiles_list;
			//list<TilesObject*>::iterator i_tiles_drawed = tiles_drawed_list->begin();

			//while (i_tiles_drawed != tiles_drawed_list->end() && is_drawed == false)
			//{
			//	tiles_drawed = *i_tiles_drawed;
			//	if (tiles == tiles_drawed)
			//	{
			//		is_drawed = true;

			//	}
			//	++i_tiles_drawed;
			//}
			////////////////////////////////////////////////////////////////////////////
			//if (is_drawed == false)
			//{
			//	//kiem tra obj nam khong qua xa camera: khac phuc tinh trang bi giat
			//	if (tiles->pos_x > camara_rect.left - 30 && tiles->pos_x < camara_rect.left + 800 + 30)
			//	{
			//		p_tiles_list->push_back(tiles);
			//	}

			//	//p_tiles_list->push_back(tiles); //hoi bi giat
			//}				
			p_tiles_list->push_back(tiles);
		}


	}
}

void QuadTree::getTilesBgFromCamara(RECT camara_rect, list<TilesObject*>* p_tiles_list)
{
	getTilesBgFromCamara(this->root, camara_rect, p_tiles_list);
}

void QuadTree::getTilesBgFromCamara(QNode *p_qnode, RECT camara_rect, list<TilesObject*>* p_tiles_list)
{

	if (p_qnode->getLeftTop() == NULL || 
		p_qnode->getRightTop() == NULL || 
		p_qnode->getLeftBottom() == NULL ||
		p_qnode->getRightBottom() == NULL)
	{
		//node con
		clipTiles(camara_rect, p_qnode, p_tiles_list);		 
	}
	else
	{
		getTilesBgFromCamara(p_qnode->getLeftTop(), camara_rect, p_tiles_list);
		getTilesBgFromCamara(p_qnode->getRightTop(), camara_rect, p_tiles_list);
		getTilesBgFromCamara(p_qnode->getLeftBottom(), camara_rect, p_tiles_list);
		getTilesBgFromCamara(p_qnode->getRightBottom(), camara_rect, p_tiles_list);
	}
}

void QuadTree::getTilesList(list<TilesObject*>* p_tiles_list)
{
	getTilesList(this->root, p_tiles_list);
}

void QuadTree::getTilesList(QNode *p_qnode, list<TilesObject*>* p_tiles_list)
{
	if (p_qnode->getLeftTop() == NULL || 
		p_qnode->getRightTop() == NULL || 
		p_qnode->getLeftBottom() == NULL ||
		p_qnode->getRightBottom() == NULL)
	{
		//node con
		
		list<TilesObject*> temp_list;
		temp_list = p_qnode->getTilesBgList();
		TilesObject *obj;
		list<TilesObject*>::const_iterator iList;// = p_qnode->getObjList().begin();
		for (iList = temp_list.begin(); iList != temp_list.end(); iList++)
		{
			obj = *iList;
			p_tiles_list->push_back(obj);			
		}		
	}
	else
	{
		getTilesList(p_qnode->getLeftTop(), p_tiles_list);
		getTilesList(p_qnode->getRightTop(), p_tiles_list);
		getTilesList(p_qnode->getLeftBottom(), p_tiles_list);
		getTilesList(p_qnode->getRightBottom(), p_tiles_list);
	}
}